1. Field of the Invention
The present invention relates to a matrix operation processing device.
2. Description of the Related Art
Currently, many data processing devices, including personal computers, are commercialized and are put into practical use. In such data processing devices, data is stored or transferred after being encoded. In particular, if digital signals are received from a storage/reproduction medium, such as a magnetic disk, an optical disk, a magneto-optical disk and the like, or a network, and are decoded, an LDPC (low density parity check) code is sometimes used for error correction.
In order to obtain a process result P using N bits of signal data string I and N×M bits of check matrix H, the matrix operation P=H*IT is needed. For example, if the following equation holds true,
                              I          =                      [                                          i                0                            ,                              i                1                            ,              Λ              ,                              i                                  N                  -                  1                                                      ]                          ,                                  ⁢                  P          =                      [                                          p                0                            ,                              p                1                            ,              Λ              ,                              p                                  M                  -                  1                                                      ]                          ,                                H        =                  [                                                                      h                  00                                                                              h                  01                                                            Λ                                                              h                                                            0                      ⁢                      N                                        -                    1                                                                                                      M                                            M                                            M                                            M                                                                                      h                                      M                    -                    10                                                                                                h                                      M                    -                    11                                                                              Λ                                                              h                                      M                    -                                          1                      ⁢                      M                                        -                    1                                                                                ]                    the process result P can be calculated as follows.
                              P          m                =                              ∑                          n              =              0                                      N              -              1                                ⁢                                    h              mn                        *                          i              n                                                          (        1        )            
In this case, for example, a magnetic disk device being a typical storage/reproduction medium is provided with an error correction function. An LDPC code is one of possibly many codes used for such error correction. In this case, calculating this code requires such a matrix operation.
A check matrix used for a parity calculation or an LDPC decoding contains only binary values (1s and 0s. In this case, equation (1) is as follows.
                              P          m                =                              ∑                          n              =                                                0                  /                                      h                    mn                                                  =                1                                                    N              -              1                                ⁢                      i            n                                              (        2        )            
FIG. 1 shows a conventional matrix operation circuit.
In order to obtain the process result P by performing such a process, equation (2) must be calculated after the full data of the signal data string I are obtained.
After all the full data of the signal data string I are stored in a register 40, a selector SEL 42 selects items, the value of which is 1 in each row read from a ROM 14 and the like storing a matrix datum H, and an adder 46 adds the items. The result of the addition is stored in a register 43. In this case, RW represents the maximum number of 1s in each row. By repeating this process M times, the process result P can be obtained. In this case, if the selector and adder are shared until the full data of P are obtained, the process runs in O(N+M) time and causes great delay, which is a problem. In this case, a storage register N with a large circuit scale and/or RW adders is also needed.
FIG. 2 shows another conventional matrix operation circuit.
In this conventional matrix operation circuit, after the full data of a signal data string I are stored in a register 44, an adder 47 wired based on the matrix H calculates the full data of the process result P. The result is stored in a register 45 and is output. In this case, although only O(N) time is needed to obtain the full of data of P, the size of a storage register N and the circuit scale become large since RW×M adders are needed, which is another problem.